%%% Copyright 2010 Google Inc.
%%%
%%% Licensed under the Apache License, Version 2.0 (the "License");
%%% you may not use this file except in compliance with the License.
%%% You may obtain a copy of the License at
%%%
%%%     http://www.apache.org/licenses/LICENSE-2.0
%%%
%%% Unless required by applicable law or agreed to in writing, software
%%% distributed under the License is distributed on an "AS IS" BASIS,
%%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
%%% See the License for the specific language governing permissions and
%%% limitations under the License.

%%% @copyright 2010 Google Inc. All Rights Reserved.
%%% @author <jacoby@google.com> Jacoby Thwaites [http://sites/madcloud]
%%% @version {@version}
%%% @doc
%%% Implementation of generalised best-first search (ie breadth-first with
%%% eval function determining priority).
%%%
%%% Requires a user module `Callback' implementing callback functions
%%% as follows:
%%%
%%%   eval(State, Context) -> integer()
%%%     where a lower eval means higher priority on the search agenda.
%%%
%%%   successors(State, Context) -> list()
%%%     being a list of successor states.
%%%
%%%   goal_reached(State, Context) -> true | false
%%%     defines whether search is complete.
%%%
%%% Successive `State's are appended to form a `Pathlist'.
%%%
%%% Named ETS tables are used for the agenda and used states.
%%%
%%% This is an Erlang rendering of an algorithm in "Artificial Intelligence
%%% through Prolog" by Neil C. Rowe published by Prentice-Hall in 1988.
-module(search).

%% Function return values.
-define(UNDEFINED, undefined).
-define(NOT_FOUND, not_found).
-define(GOAL_REACHED, goal_reached).
-define(GOAL_NOT_REACHED, goal_not_reached).

%%% ETS named tables and records.
-define(AGENDA, search_agenda).
-define(USED, search_used_state).

%%% Exported functions.
-export([search/2]).

%%% These records are stored in ETS tables to represent the agenda,
%%% usedstates and beststate respectively.
-record(?AGENDA, {state = ?UNDEFINED,
                  pathList = [],
                  eval = ?UNDEFINED}).

-record(?USED, {state = ?UNDEFINED}).

%% @doc Returns the path list of states that reach a goal state.
%% The `Start' term can be anything representing the start state.
%% The `Callback' can be an atom or a tuple.
%%
%% If the start state is a goal state, then returns a singleton list.
%% If no path can be found, then returns empty list.
%% Otherwise returns list of successive states including the start state.
%%
%% If an atom, `Callback' is simply a module name, and callback functions
%% are invoked with an empty static `Context' argument.
%%
%% If a tuple `{Module, Context}', it comprises an atom specifying a callback
%% module and static context data (which can be anything) that is
%% passed in callbacks for user-specified purposes.
%%
%% For example, the user might want to include the current goal in the context
%% to enable the eval function to compute an estimate of how close the current
%% state is.
%% <ul>
%%   <li>`Callback:eval(State, Context) -> integer()'</li>
%%   <li>`Callback:successors(State, Context) -> list()'</li>
%%   <li>`Callback:goal_reached(State, Context) -> true | false'</li>
%% </ul>
%% @spec search(term(), {atom(), term()}) -> list()
search(Start, Module) when is_atom(Module) ->
  search(Start, {Module, []});

%% #2
search(Start, {Module, _Context} = Callback) when is_atom(Module) ->
  Db = new_database(),
  add_state(Db, Callback, Start, []),
  Result =
    case process_agenda(Db, Callback) of
      ?NOT_FOUND ->
        [];
      #?AGENDA{pathList = PathList} ->
        lists:reverse(PathList)
      end,
  kill_database(Db),
  Result.

%% @doc Creates new ETS named tables and returns their IDs
%% @spec new_database() -> {term(), term()}
new_database() ->
  {ets:new(?AGENDA, [{keypos, #?AGENDA.state}]),
   ets:new(?USED, [{keypos, #?USED.state}])}.

%% @doc Deletes the ETS named tables. These are deleted automatically when
%% the process crashes out.
%% @spec kill_database({term(), term()}) -> ok
kill_database({Agenda, Used}) ->
  ets:delete(Agenda),
  ets:delete(Used),
  ok.

%% @doc Adds state to agenda if neither already used nor already on agenda.
%% @spec add_state(db(), atom(), term(), list()) -> ok
add_state({Agenda, Used}, {Module, Context}, NewState, PathList) ->
  NewEval = Module:eval(NewState, Context),
  case {is_used(Used, NewState), get_agenda(Agenda, NewState)} of
    {false, ?NOT_FOUND} ->
      add_agenda(Agenda, NewState, [NewState | PathList], NewEval);
    _Other ->
      ok
  end.

%% @doc Adds a record whose key is `State' to the used table.
%% @spec add_used(used(), term()) -> ok
add_used(Used, State) ->
  ets:insert(Used, #?USED{state = State}),
  ok.

%% @doc Returns true if the state exists in the used state table, otherwise
%% false.
%% @spec is_used(used(), term()) -> true | false
is_used(Used, State) ->
  case ets:lookup(Used, State) of
    [] -> false;
    _Other -> true
  end.

%% @doc Returns the agenda record matching `State', or not_found.
%% @spec get_agenda(agenda(), term()) -> #agenda{} | not_found
get_agenda(Agenda, State) ->
  case ets:lookup(Agenda, State) of
    [] -> ?NOT_FOUND;
    [AgendaRecord] -> AgendaRecord
  end.

%% @doc Adds a state with path and eval to the agenda.
%% @spec add_agenda(agenda(), term(), list(), integer()) -> ok
add_agenda(Agenda, State, PathList, Eval) ->
  ets:insert(Agenda, #?AGENDA{state = State,
                               pathList = PathList,
                               eval = Eval}),
  ok.

%% @doc Removes the agenda record for key `State' from the table.
%% @spec remove_agenda(agenda(), term()) -> ok
remove_agenda(Agenda, State) ->
  ets:delete(Agenda, State),
  ok.

%% @doc Processes the agenda (which is an ETS table). This tail-recurses until
%% the agenda is empty or a goal is reached.
%% Returns `not_found' if no goal is reached, or the agenda record (including
%% state and path) if a goal is reached.
%% @spec process_agenda(db(), atom()) -> #agenda{} | not_found
process_agenda({Agenda, _Used} = Db, Callback) ->
  case pick_best_state(Agenda) of
    ?NOT_FOUND ->
      ?NOT_FOUND;
    #?AGENDA{state = State, pathList = PathList} ->
      case add_successors(Db, Callback, State, PathList) of
        ?GOAL_REACHED ->
          get_agenda(Agenda, State);
        ?GOAL_NOT_REACHED ->
          process_agenda(Db, Callback)
      end
    end.

%% @doc Adds all successor states to `State' to the agenda. If `State' is a goal
%% state, then returns `goal_reached', otherwise returns `goal_not_reached'.
%% @spec add_successors(db(), atom(), term(), list()) ->
%%          goal_reached | goal_not_reached
add_successors({Agenda, Used} = Db, {Module, Context} = Callback,
               State, PathList) ->
  case Module:goal_reached(State, Context) of
    true ->
      ?GOAL_REACHED;
    false ->
      [add_state(Db, Callback, Successor, PathList) ||
         Successor <- Module:successors(State, Context)],
      remove_agenda(Agenda, State),
      add_used(Used, State),
      ?GOAL_NOT_REACHED
    end.

%% @doc Returns the agenda item with the lowest eval. We're stepping through
%% the table here, which is not very pretty hence:
%% @todo (jacoby) Refactor to use sorted queue.
%% @spec pick_best_state(agenda()) -> #agenda{} | not_found
pick_best_state(Agenda) ->
  case ets:first(Agenda) of
    '$end_of_table' ->
      ?NOT_FOUND;
    FirstKey ->
      pick_best_state(Agenda, FirstKey, #?AGENDA{})
  end.

%% @doc Returns the agenda record represented by `Key' or one of its
%% successors, if eval is less than `BestSoFar', otherwise returns `BestSoFar'.
%% @spec pick_best_state(agenda(), term(), #agenda{}) -> #agenda{}
pick_best_state(Agenda, Key, #?AGENDA{eval = BestEval} = BestSoFar) ->
  [#?AGENDA{eval = Eval}] = [Record] = ets:lookup(Agenda, Key),
  case {BestEval =:= ?UNDEFINED orelse Eval < BestEval,
        ets:next(Agenda, Key)} of
    {true, '$end_of_table'} ->
      Record;
    {false, '$end_of_table'} ->
      BestSoFar;
    {true, NextKey} ->
      pick_best_state(Agenda, NextKey, Record);
    {false, NextKey} ->
      pick_best_state(Agenda, NextKey, BestSoFar)
  end.
